﻿using System;
using Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.SequenceComparison.DTW
{
    public class DynamicTimeWarper<T>
    {
        private readonly Func<T, T, double> _distanceFunction;

        public DynamicTimeWarper(Func<T,T,double> distanceFunction)
        {
            _distanceFunction = distanceFunction;
        }

        public double Distortion(IList<T> a, IList<T> b)
        {
            var D = new double[a.Count][];
            for(int i = 0; i < a.Count; i++)
            {
                D[i] = new double[b.Count];
            }
            D[0][0] = _distanceFunction(a[0], b[0]);
            for(int i = 1; i < a.Count; i++)
            {
                D[i][0] = D[i - 1][0] + _distanceFunction(a[i], b[0]);
            }
            for(int j = 1; j < b.Count; j++)
            {
                D[0][j] = D[0][j - 1] + _distanceFunction(a[0], b[j]);
                for(int i = 1; i < a.Count; i++)
                {
                    D[i][j] = Math.Min(D[i - 1][j - 1], D[i][j - 1]);
                    D[i][j] = Math.Min(D[i][j], D[i - 1][j - 1]) + _distanceFunction(a[i], b[j]);
                }
            }
            return D[a.Count - 1][b.Count - 1];
        }
    }
}
